package com.googlecode.gaal.data.impl;

import java.util.Arrays;

import com.googlecode.gaal.data.api.IntSequence;

public class SparseSequence extends AbstractSequence {

    protected final int[] indices;
    protected final int[] data;
    private int size;

    public SparseSequence(int capacity) {
        indices = new int[capacity];
        data = new int[capacity];
    }

    public void put(int index, int value) {
        int i = size - 1;
        while (i >= 0 && index < indices[i]) {
            indices[i + 1] = indices[i];
            data[i + 1] = data[i];
            i--;
        }
        indices[i + 1] = index;
        data[i + 1] = value;
        size++;
    }

    @Override
    public int get(int index, int defaultValue) {
        int pos = Arrays.binarySearch(indices, 0, size, index);
        if (pos < 0)
            return defaultValue;
        else
            return data[pos];
    }

    @Override
    public int get(int index) throws IndexOutOfBoundsException {
        int pos = Arrays.binarySearch(indices, 0, size, index);
        if (pos < 0)
            throw new IndexOutOfBoundsException("" + index);
        else
            return data[pos];
    }

    @Override
    public IntSequence subSequence(int start, int end) throws IndexOutOfBoundsException {
        throw new UnsupportedOperationException();
    }

    @Override
    public IntSequence reverse() {
        throw new UnsupportedOperationException();
    }

    @Override
    public int size() {
        return size;
    }
}
